package primary.primary0;

import java.util.Arrays;

/**
 *
 */
public class S0031下一个排列 {
    /**
     * 100
     */
    class Solution2 {
        public void nextPermutation(int[] nums) {
            int loc1 = nums.length;
            // 待替换的点
            for(int i = nums.length - 2; i >= 0; i--){
                if(nums[i] < nums[i + 1]){
                    loc1 = i;
                    break;
                }
            }
            if(loc1 == nums.length){
                for(int i = 0; i < nums.length/2; i++){
                    swap(nums, i, nums.length - 1 - i);
                }
                return;
            }
            int loc2 = 0;
            // 比它大的最小的值
            for(int i = nums.length - 1; i >= 0; i --){
                if(nums[i] > nums[loc1]){
                    loc2 = i;
                    break;
                }
            }
            // System.out.println("loc1 " + loc1 + " loc2 " + loc2);
            swap(nums, loc1, loc2);
            // 后面变成最小形式排列
            for(int i = 0; i < (nums.length - loc1) / 2; i++){
                swap(nums, loc1 + 1 + i, nums.length - 1 - i);
            }
        }
        private void swap(int[] nums, int a, int b){
            int temp = nums[a];
            nums[a] = nums[b];
            nums[b] = temp;
        }
    }

    /**
     * 答案，
     * 要从逻辑出发，就是要把一个较小的值，换成它后面的较大的值
     * 1. 较小的值尽量靠右
     * 2. 换到的那个较大的值，尽量小
     * 注意这要找到的第一个较小值，他的后面那一排一定是递减的，而且把它换过去，还是递减的
     * 所以
     * 1. i是从右到左第一个开始减的值
     * 2. nums[j]是从右到i第一个比nums[i]大的值
     */
    class Solution {
        public void nextPermutation(int[] nums) {
            int i = nums.length - 2;
            while (i >= 0 && nums[i] >= nums[i + 1]) {
                i--;
            }
            if (i >= 0) {
                int j = nums.length - 1;
                while (j >= 0 && nums[i] >= nums[j]) {
                    j--;
                }
                swap(nums, i, j);
            }
            reverse(nums, i + 1);
        }

        public void swap(int[] nums, int i, int j) {
            int temp = nums[i];
            nums[i] = nums[j];
            nums[j] = temp;
        }

        public void reverse(int[] nums, int start) {
            int left = start, right = nums.length - 1;
            while (left < right) {
                swap(nums, left, right);
                left++;
                right--;
            }
        }
    }





    /**
     * 97, 题目晦涩难懂, 直觉告诉我意外条件比较多
     * 用例 100->001 即没有下一个排列
     */
    public static void nextPermutation(int[] nums) {
        // 检查是否为降序
        int cur = 100;
        boolean descFlag = true;
        for (int num : nums) {
            if(num > cur) descFlag = false;
            cur = num;
        }
        if(descFlag){
            Arrays.sort(nums);
            return;
        }
        // 存在下一个排列, 从后往前找到第一个可以被后面替换的值, 做一个最小的替换, 然后把剩下的值做一个升序排列
        // 常数空间, 不能用队列, 也可以用队列, 但是看到重复的值, 就存一个, 然后就是常数空间了, 或者使用visited数组代替
        int[] visitedLoc = new int[100]; // 存储每一个位置第一次出现的位置
        Arrays.fill(visitedLoc, -1);
        for (int posi = nums.length - 1; posi >= 0; posi--) {
            for(int j = nums[posi] + 1; j <= 99; j++){
                // 后面最小的比他大的值
                if(visitedLoc[j] >= 0){
                    swap(nums, posi, visitedLoc[j]);
                    Arrays.sort(nums, posi + 1, nums.length);
                    return;
                }
            }
            visitedLoc[nums[posi]] = posi;
        }

    }


    public static void swap(int[] nums, int start, int end){
        int temp = nums[start];
        nums[start] = nums[end];
        nums[end] = temp;
    }

    public static void main(String[] args) {
        int[] input = new int[]{1, 4, 3, 2, 1};
        nextPermutation(input);
        System.out.println(Arrays.toString(input));
    }
}
